# This script applies the Dijkstra algorithm to identify 
# for every data object the shortest path from source 
# to all nodes that received the data object.

# resulting file:
# 

BEGIN {
	cnt = 0;
	cntNodes = 0;
}

{
	dobjId = $1;
	delay = $2;
	nodeIdSrc = $3;  	# node on which we observe send_success
	nodeIdDst = $4;
	recTime = $5;

	# set first dobjIdCurrent	
	if (FNR == 1) dobjCurrent = dobjId;

	# get node index for nodeIdSrc, nodeIdDst
	nodeSrc = -1;
	nodeDst = -1;
	# find out the node number 
	for (n=0;n<cntNodes;n++) {
		if (Nodes[n] == nodeIdSrc) {
			nodeSrc = n;
		}
		if (Nodes[n] == nodeIdDst) {
			nodeDst = n;
		}
	}
	# can not find nodeSrc/Dst so this is a new node
	if (nodeSrc == -1) {
		Nodes[cntNodes] = nodeIdSrc;
		nodeSrc = cntNodes;
		print "new nodeId (src) " cntNodes , "[" nodeIdSrc "]";
		cntNodes++;
	}
	if (nodeDst == -1) {
		Nodes[cntNodes] = nodeIdDst;
		nodeDst = cntNodes;
		print "new nodeId (dst) " cntNodes, "[" nodeIdDst "]";
		cntNodes++;
	}

	# is new dObj or EOF
	if (dobjId != dobjCurrent) {
		delete N_t;
		delete D;  # delay
		delete H;  # hop
		cntN_t = 0;
		initValue = 99999;

		print " ";

#		for (s=0;s<cnt;s++) {
#			print src[s], dst[s], del[s];
#		}

#		print " ";

		# find source node (nodeSrc not in nodeDst)
		srcIdx = -1;
		for (s=0;s<cnt;s++) {
			if (srcIdx == -1) {
				found = 0;
				for (d=0;d<cnt;d++) {
					if (src[s] == dst[d]) {
						found++;
					}
				}
				if (found == 0) srcIdx = src[s];
			}
		}
		# not found > use time
		# just now: always use time (ok for testbed)
#		if (srcIdx == -1) {
			minTimeIdx = -1;
			for (s=0;s<cnt;s++) {
				if (tim[s] < minTime || minTimeIdx == -1) {
					minTime = tim[s];
					minTimeIdx = src[s];
				}
			}
			if (minTimeIdx > -1) {
				srcIdx = minTimeIdx;
#				print "source via time", Nodes[minTimeIdx];
			}
#		}
		print "source:", Nodes[srcIdx];

		# Dijkstra init
		N_t[cntN_t++] = srcIdx;
		for (n=0;n<cntNodes;n++) {
			D[n] = initValue;
			H[n] = initValue;
		}		
		for (n=0;n<cnt;n++) {
			if (src[n] == srcIdx) {
				D[dst[n]] = del[n];
				H[dst[n]] = 1;
			}
		}

#		print "Dijkstra " dobjCurrent;
		candidate = initValue;
		whileCond = 1;
		while (whileCond) {

#			for (n=0;n<cntNodes;n++) {
#				print n, D[n], H[n];
#			}		
#			print " ";

			# Dijkstra algorithm
			minD = initValue;
			candidate = -1;
			# find m not in N' such that D(m) is a minimum
			for (m=0;m<cntNodes;m++) {
				inN_t = 0;
				for (n=0;n<cntN_t;n++) {
					if (N_t[n] == m) inN_t = 1;
				}
				if (inN_t == 0) {
					if (minD > D[m]) {
						minD=D[m];
						candidate = m;
					}
				}
			}
			if (candidate > -1) {
				m = candidate;
	
#				print "candidate", m, minD;
	
				# add m to N'
				N_t[cntN_t++] = m;
				
				# update D(n) for each neighbor n of m and not in N'
				for (n=0;n<cntNodes;n++) {
					# in N' ?
					inN_t = 0;
					for (i=0;i<cntN_t;i++) {
						if (N_t[i] == n) inN_t = 1;
					}
					if (inN_t == 0) {
						for (i=0;i<cnt;i++) {
							# neighbor ?
							if (src[i] == m && dst[i] == n) {
#								print "  update", n;
								# update
								a = D[n];
								b = D[m]+del[i];
								D[n] = (a>b ? b : a);
								H[n] = (a>b ? H[m]+1 : H[n]);
#								print "   >", D[n];
							}
						}
					}
				}
			} else {
				break;
			}
			
			# update while condition
			whileCond = 0;
			if (cntN_t < cntNodes) whileCond = 1;
			if (candidate < 0) whileCond = 0;
			
		}
		

		# print summary
		invResistanceDelay = 0;
		invResistanceHop = 0;
		for (n=0;n<cntNodes;n++) {
			if (n == srcIdx) {
				print dobjCurrent, "node", Nodes[n], 0, 0;
			}
			if (D[n] < initValue) {
				print dobjCurrent, "node", Nodes[n], D[n], H[n];
				
				if (D[n]!=0 && H[n]!=0){
				  invResistanceDelay += 1/D[n];
				  invResistanceHop += 1/H[n];
				}
			}
		}
		if (invResistanceDelay > 0) print dobjCurrent, "r_delay", 1/invResistanceDelay;
		if (invResistanceHop > 0) print dobjCurrent, "r_hop", 1/invResistanceHop;


		# reset
		delete src;
		delete dst;
		delete hop;
		delete del;
		delete tim;
		cnt=0;

		dobjCurrent = dobjId;
	}

	src[cnt] = nodeSrc;
	dst[cnt] = nodeDst;
	hop[cnt] = 1;
	del[cnt] = delay;
	tim[cnt] = recTime;
	cnt++;
}